package offer.day5;

import java.util.Arrays;

public class No7construct {
    /*
     * 面试题7：重建二叉树
     *    题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
     *        假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。
     *        例如：输入前序遍历序列{1，2，4，7，3，5，6，8}和中序遍历序列{4，7，2，1，5，3，8，6}，
     *            则重建二叉树并输出它的头节点
     *        二叉树节点的定义：
     *        struct BinaryTreeNode{
     *        	int m_nValue;            //value
     *        BinaryTreeNode* m_pLeft;   //左子树
     *        BinaryTreeNode* m_pRight;  //右子树
     *        }
     *
     *   思路：先找出根节点，然后利用递归方法构造二叉树
     * */

    public static void main(String[] args) {
        No7construct c=new No7construct();
        int[] pre = {1,2,4,7,3,5,6,8};//前序遍历序列
        int[] in = {4,7,2,1,5,3,8,6};//中序遍历序列
        TreeNode root=c.Construct(pre,in);
        c.postOrder(root);


    }

    public void postOrder(TreeNode root){
        if(root==null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    public TreeNode Construct(int[] pre,int[] in){
        if(pre==null||in==null) return null;
        if(pre.length==0||in.length==0) return null;
        if(pre.length!=in.length) return null;
        TreeNode root=new TreeNode(pre[0]);
        for(int i=0;i<in.length;i++){
            if(in[i]==pre[0]){
                root.left=Construct(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right=Construct(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return root;
    }
}

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val){
        this.val = val;
    }

}
